Asynchronous Transfer Mode (ATM) networks have become increasingly popular for both wide area networks and local area networks. In an ATM network all information is transported through the network in relatively short blocks called cells. Information flow through the network is along paths called virtual channels which are set up as a series of pointers through the network. Cells on a particular virtual channel always follow the same path through the network and are delivered to the destination in the order in which they are received.
When communications are initiated in an ATM network a request is made for a connection. As part of the connection request, the quality of service (QoS) of the request is specified by the requester. Quality of service characteristics which may be specified in ATM include cell transfer delay (network latency), cell delay variation (jitter), cell transfer capacity (average and peak allowed rates), cell error ratio, cell loss ratio and cell misinsertion ratio. These QoS parameters are used by the ATM nodes to determine the route of the connection and in determining allowable node utilization.
Routing in an ATM network is performed by an ATM node which attempts to predict the route for a virtual connection from a source to a destination. An ATM connection is not set up unless and until the network determines that there is sufficient capacity for the new connection. This determination is based upon the characteristics of the network, the existing traffic on the network and the requested QoS for the connection. If the requested QoS cannot be provided then the requested connection is not accepted. The function in ATM which determines whether a connection request is accepted is referred to as call admission control (CAC). In ATM, the CAC function is typically carried out at two places; the entry point into the ATM network and at each node in the connection path.
At the entry point into the ATM network a process called Generic Call Admission Control (GCAC) determines a probable route for the connection request based on the QoS requested, and either accepts or rejects the request based on this determination. To perform the GCAC function, the entry point should have available information about the utilization of the other nodes in the ATM network. This information may then be utilized to determine if the nodes along the selected route can satisfy the QoS requirements of the requested connection.
At each node in a connection route, a local call admission control function, called an Actual Call Admission Control (ACAC), determines if the node will accept the connection request. This ACAC function utilizes the requested QoS and information about the existing connections through the node to determine if the requested QoS level may be achieved. If so, the connection request is accepted.
To have sufficient information to perform the GCAC function at each possible entry point, each node in the network broadcasts information about each connection at the node. This information typically includes information sufficient to determine the traffic envelope for a connection (i.e. the maximum amount of traffic a connection is allowed to send in time). Information sufficient to calculate the traffic envelope for a connection includes the peak data rate for the connection, the maximum burst size, the maximum sustained data rate and the guaranteed delay. From this information, the node may perform a "schedulability" to determine if the nodes in the proposed route will probably accept the requested connection.
While the GCAC function may provide increased performance in routing, one drawback is the increase in overhead associated with broadcasting connection information over the ATM network to each node for each connection. As the number of connections at a node increase the amount of overhead for broadcasting connection information increases. With a large number of connections, significant amounts of bandwidth of a network may be consumed with connection data transmissions from node to node.
In an effort to ensure that accepted connections provide the requested quality of service criteria for a connection, ATM nodes may utilize an Earliest Deadline First (EDF) scheduler to select the order in which cells are transmitted over a physical link of the network. The EDF scheduler prioritizes cells on a physical link based upon the time until the maximum delay time through the node of the cell expires. By transmitting the cells with the least time left until the maximum delay time expires, the likelihood of making the maximum delay criteria is increased. However, such scheduling may require significant processing. For example, all cells in the system may be queued but then all cells must be searched for the shortest deadline. Alternatively, maintenance of a single sorted queue of all the cells in the system would require log N operations to insert a cell in the queue, where N is the number of cells in the queue.
Whatever system of scheduling cells to meet the maximum delay requirements is utilized, congestion conditions may still result in the ATM network. In an ATM network, congestion control is provided by discarding cells until the congestion problem is relieved. To facilitate minimizing the disruption caused by such discarding of cells, a cell may be marked as a low priority cell. Low priority cells would be the first cells to be discarded to relieve a congestion problem. FIG. 1 illustrates the configuration of a cell in ATM. As seen in FIG. 1, the cell loss priority bit (CLP) may be set to indicate that the cell may be discarded. This ability to prioritize cells to be discarded may further complicate an EDF scheduler as the scheduler should also take into account whether a cell with a short deadline is a low priority cell and whether higher priority cells are waiting to be transmitted.
In light of the above discussion, a need exists for improvements in the mechanisms for accepting connections and for scheduling transmission of cells for accepted connections in ATM networks.